package exam.microsoft.first.task2;

/**
 * @Author: 18362
 * @Create: 2022-08-19 18:57:05 星期五
 */
class Solution {
    public String solution(String S) {
        int[] cnt = new int[10];
        String[] strs = new String[10];
        for (int i=0; i<10; ++i)
            strs[i] = String.valueOf((char) (i + '0'));
        for (int i=0; i<S.length(); ++i)
            cnt[S.charAt(i)-'0']++;
        int maxNum = -1, maxMoreNum = -1;
        for (int i=0; i<cnt.length; ++i) {
            if (cnt[i] > 0)
                maxNum = i;
            if (cnt[i] > 1)
                maxMoreNum = i;
        }
        if (maxMoreNum <= 0)
            return strs[maxNum];
        StringBuilder res = new StringBuilder();
        String[] buf = new String[10];
        for (int i=maxMoreNum; i>=0; --i) {
            if (cnt[i] > 1) {
                int num = cnt[i] / 2;
                StringBuilder temp = new StringBuilder(num);
                for (int j=0; j<num; ++j)
                    temp.append(strs[i]);
                buf[i] = temp.toString();
                res.append(buf[i]);
            }
        }
        for (int i=9; i>=0; --i) {
            if (cnt[i] % 2 == 1) {
                res.append(strs[i]);
                break;
            }
        }
        for (int i=0; i<=maxMoreNum; ++i) {
            if (cnt[i] > 1)
                res.append(buf[i]);
        }
        return res.toString();
    }
}
